11092. Минимальная строка

Финес и Ферб очень хотят попасть в титры, которые хранятся на компьютере у Кэндис. Им известно, что Кэндис боится забыть пароль, поэтому она хранит подсказку: две строки a и b, состоящие из строчных английских букв.

Сегодня утром Ферб узнал правило, по которому из подсказки можно получить сам пароль.

Рассмотрим следующую операцию:

· Выберем любую позицию в строке a. Выберем любую позицию в строке b.

· Символы на этих позициях поменяем местами.

Паролем является лексикографически минимальная строка a, которую можно получить в результате применения произвольного числа таких операций. Помогите ребятам вычислить пароль.

Вход. В первой строке задана строка a, во второй строке – строка b (1 ≤ |a|, |b| ≤ 10⁵). Обе строки состоят из строчных английских букв.

Выход. Выведите найденный пароль.

Пример входа	Пример выхода
hello myworld	dehll

РЕШЕНИЕ

строки

Анализ алгоритма

Лексикографически наименьшие буквы всегда можно вставить в строку a (на любую позицию) при помощи описанной операции.

Объединим строки a и b. Пусть s = a + b. Отсортируем буквы строки s по возрастанию. Лексикографически наименьшие буквы окажутся в начале строки s. Если строка a содержит k букв, то паролем будет префикс строки s длины k.

Реализация алгоритма

Читаем входные строки a и b.

cin >> a;

cin >> b;

Объединяем строки a и b и сортируем результирующую строку.

s = a + b;

sort(s.begin(), s.end());

Выводим ответ – префикс строки s длины a.size().

cout << s.substr(0, a.size());

Python реализация

Читаем входные строки a и b.

a = input()

b = input()

Объединяем строки a и b.

s = a + b

Сортируем строку s.

s = ''.join(sorted(s))

Выводим ответ – префикс строки s длины len(a).

print(s[:len(a)])